<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="QNxz2" id="QNxz2"><span data-lake-id="u32efe841" id="u32efe841">典型回答</span></h1>
  <p data-lake-id="u9db64d27" id="u9db64d27"><br></p>
  <p data-lake-id="u832fae5a" id="u832fae5a"><span data-lake-id="u03364956" id="u03364956">为什么需要扩容？假设现在散列表中的元素已经很多了，但是现在散列表的链化已经比较严重了，哪怕是树化了，时间复杂度也没有O(1)好，所以需要扩容来降低Hash冲突的概率，以此来提高性能。</span></p>
  <p data-lake-id="u0f580889" id="u0f580889"><span data-lake-id="u9120ddc7" id="u9120ddc7">​</span><br></p>
  <p data-lake-id="uedddc658" id="uedddc658"><span data-lake-id="ua7ff7a2f" id="ua7ff7a2f">我们知道，当</span><code data-lake-id="uca67f5b4" id="uca67f5b4"><span data-lake-id="u137dc057" id="u137dc057">++size &gt; threshold </span></code><span data-lake-id="ue6868dd5" id="ue6868dd5">之后(详见java.util.HashMap#putVal方法)，HashMap就会初始化新的新的桶数组，该桶数组的size为原来的两倍，在扩大桶数组的过程中，会涉及三个部分：</span></p>
  <ol list="uc3a55200">
   <li fid="ub4b195a1" data-lake-id="u91a0fecf" id="u91a0fecf"><span data-lake-id="u11b640a8" id="u11b640a8">如果某桶节点没有形成链表，则直接rehash到其他桶中</span></li>
   <li fid="ub4b195a1" data-lake-id="u2a96113a" id="u2a96113a"><span data-lake-id="u96310822" id="u96310822">如果桶中形成链表，则将链表重新链接</span></li>
   <li fid="ub4b195a1" data-lake-id="ud6d6909b" id="ud6d6909b"><span data-lake-id="u7480c8d0" id="u7480c8d0">如果桶中的链表已经形成红黑树，但是链表中的元素个数小于6，则进行取消树化的操作</span></li>
  </ol>
  <h2 data-lake-id="WlzME" id="WlzME"><span data-lake-id="u00a0f359" id="u00a0f359">桶元素重新映射</span></h2>
  <p data-lake-id="ud370ef6b" id="ud370ef6b"><span data-lake-id="ue9b7dbf8" id="ue9b7dbf8">如果桶中只有一个元素，没有形成链表，则将原来的桶引用置为null，同时，将该元素进行rehash即可，如下代码所示：</span></p>
  <pre lang="java"><code>
if (e.next == null) {
    newTab[e.hash &amp; (newCap - 1)] = e;
}
</code></pre>
  <h2 data-lake-id="KrQrW" id="KrQrW"><span data-lake-id="u1d7cffba" id="u1d7cffba">链表重新链接</span></h2>
  <p data-lake-id="uf7d07321" id="uf7d07321"><span data-lake-id="ua891c634" id="ua891c634">假设有4个key，分别为a，b，c，d，且假定他们的hash值如下：</span></p>
  <pre lang="java"><code>
hash(a) = 3; hash(a) &amp; 7 = 3;   hash(a) &amp; 8 = 0; 
hash(b) = 11; hash(b) &amp; 7 = 3;  hash(b) &amp; 8 = 8; 
hash(c) = 27; hash(c) &amp; 7 = 3;  hash(c) &amp; 8 = 8;  
hash(d) = 59; hash(d) &amp; 7 = 3;  hash(d) &amp; 8 = 8; 
</code></pre>
  <p data-lake-id="u3f26a4ef" id="u3f26a4ef"><span data-lake-id="u2b98165c" id="u2b98165c">假如此时HashMap的cap为8，某个桶中已经形成链表，则可得到：table[3]=a-&gt;b-&gt;c-&gt;d</span></p>
  <p data-lake-id="u7f830c34" id="u7f830c34"><span data-lake-id="u8b257ea8" id="u8b257ea8">如果此时扩容，将newCap设为16，我们可以看到如下结果：</span></p>
  <pre lang="java"><code>
hash(a) = 3; hash(a) &amp; 15 = 3; 
hash(b) = 11; hash(b) &amp; 15 = 11
hash(c) = 27; hash(c) &amp; 15 = 11
hash(d) = 59; hash(d) &amp; 15 = 11
</code></pre>
  <p data-lake-id="u30b5e6f4" id="u30b5e6f4"><br></p>
  <p data-lake-id="u614cb7a6" id="u614cb7a6"><strong><span data-lake-id="u66b3827b" id="u66b3827b">我们会发现，当hash(k) &amp; oldCap = 0（即hash(a) = 3;的这个记录）时，这些链表的节点还是在原来的节点中（扩容后他的结果还是3），同时如果hash(k) &amp; oldCap != 0时（11 27 59这几条记录），这些链表的节点会到桶中的其他的位置中（从3变成了11）。</span></strong></p>
  <p data-lake-id="u93be4d41" id="u93be4d41"><br></p>
  <p data-lake-id="u7fba0d42" id="u7fba0d42"><span data-lake-id="u14635e33" id="u14635e33">所以，对于链表来说，我们就不用逐个节点重新映射，而是直接通过hash(k) &amp; oldCap进行分类，之后统一移动他们的位置即可。源码如下：</span></p>
  <pre lang="java"><code>
Node&lt;K,V&gt; loHead = null, loTail = null;
Node&lt;K,V&gt; hiHead = null, hiTail = null;
Node&lt;K,V&gt; next;
do {
    next = e.next;
    if ((e.hash &amp; oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}
</code></pre>
  <h2 data-lake-id="GTJ8h" id="GTJ8h"><span data-lake-id="u156730eb" id="u156730eb">取消树化</span></h2>
  <p data-lake-id="u2211323b" id="u2211323b"><span data-lake-id="u3dea391e" id="u3dea391e">有了上面链表重新连接的经验，我们会发现，其实树化后的节点，也可以使用该操作来降低红黑树每个节点rehash时的时间复杂度，所以红黑树的TreeNode继承了链表的Node类，有了next字段，这样就可以像链表一样重新链接，源码如下：</span></p>
  <pre lang="java"><code>
TreeNode&lt;K,V&gt; loHead = null, loTail = null;
TreeNode&lt;K,V&gt; hiHead = null, hiTail = null;
for (TreeNode&lt;K,V&gt; e = b, next; e != null; e = next) {
    next = (TreeNode&lt;K,V&gt;)e.next;
    e.next = null;
    if ((e.hash &amp; bit) == 0) {
        if ((e.prev = loTail) == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
        ++lc;
    }
    else {
        if ((e.prev = hiTail) == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
        ++hc;
    }
}
</code></pre>
  <p data-lake-id="u267f443d" id="u267f443d"><span data-lake-id="u666332f3" id="u666332f3">当上面的操作完结后，HashMap会检测两个链表的长度，当元素小于等于6的时候，就会执行取消树化的操作，否则就会将新生成的链表重新树化。</span></p>
  <p data-lake-id="u12c059ae" id="u12c059ae"><span data-lake-id="u43752b38" id="u43752b38">取消树化非常简单，因为之前已经是条链表了，所以只需要将里面的元素由TreeNode转为Node即可</span></p>
  <blockquote data-lake-id="u7dea66ec" id="u7dea66ec">
   <p data-lake-id="uec9cb1e0" id="uec9cb1e0"><span data-lake-id="ue3b8ad5a" id="ue3b8ad5a">至于重新树化的过程，请听下回分解～</span></p>
  </blockquote>
  <h1 data-lake-id="UYGCZ" id="UYGCZ"><span data-lake-id="u0762c139" id="u0762c139">知识扩展</span></h1>
  <h2 data-lake-id="QtWYr" id="QtWYr"><span data-lake-id="u4e75671f" id="u4e75671f">除了rehash之外，哪些操作也会将树会退化成链表？</span></h2>
  <p data-lake-id="u5c158220" id="u5c158220"><span data-lake-id="u8bed3eff" id="u8bed3eff">在remove元素的时候，这个过程中也会做退化的判断，如以下代码中，也会在这个分支中执行退化的操作（untreeify），如下代码所示：</span></p>
  <pre lang="java"><code>
if (root == null || (movable &amp;&amp; (root.right == null || (rl = root.left) == null|| rl.left == null))) {
  	tab[index] = first.untreeify(map);  // too small
    return;
}
</code></pre>
  <p data-lake-id="u1c1286d3" id="u1c1286d3"><br></p>
 </body>
</html>